package coding.with_data_structure;

public class KMP {

    public static void main(String[] args) {
        int i = index_KMP("qwertyuiop", "ertyu", 1);
        System.out.println(i);
    }

    /**
     * 返回子串T在主串S中第pos个字符之后的位置。若不存在，返回0
     *
     * @param S   主串
     * @param T   子串
     * @param pos
     * @return
     */
    private static int index_KMP(String S, String T, int pos) {
        int i = pos;
        int j = 1;
        int[] next = new int[255];
        getNext(T, next);
        while (i <= S.length() && j <= T.length()) {
            if (j == 0 || S.charAt(i) == T.charAt(j)) {
                ++i;
                ++j;
            } else {
                j = next[j];
            }
        }
        if (j > T.length()) {
            return i - T.length();
        }
        return 0;
    }

    /**
     * 通过计算返回子串T的next数组
     *
     * @param T
     * @param next
     */
    private static void getNext(String T, int[] next) {
        int i = 1, j = 0;
        next[0] = 0;
        while (i < T.length()) {
            if (j == 0 || T.charAt(i) == T.charAt(j)) {
                ++i;
                ++j;
            } else {
                j = next[j];
            }
        }
    }

}
